lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

index.md (2505B)

      1 +++
      2 title = 'File system layout'
      3 +++
      4 # File system layout
      5 on real disk, there are number of partitions (primary, extended, subpartitions). each partition can hold different filesystem
      6 
      7 ![](680ce86101ebb0f5559e3c485512297d.png)
      8 
      9 one partition is flagged as 'active' partition.
     10 MBR has boot code to locate active primary partition and execute boot block
     11 
     12 partitions: primary, extended, and subpartitions
     13 
     14 ## How to store files on disk
     15 
     16 contiguous allocation:
     17 
     18 - files as contiguous stream of bytes
     19 - but prone to fragmentation, requires max file size
     20 
     21 block-based (logically contiguous, but actually stored anywhere on disk):
     22 
     23 - linked list
     24     - by keeping in-band metadata, end up with strange block size (2 or 4 kb data, with some bytes to hold pointer)
     25     - good for sequential access patterns, but random...not so much
     26     - pointers are pointing to blocks on disk (NOT memory)
     27     - ![](4cec0a62f74e7cce20c9970d024cf93b.png)
     28 - file allocation table (FAT)
     29     - move in-band metadata out of band
     30     - the table is stored in kernel memory
     31     - holds starting points of files
     32     - every row refers to a block of memory
     33     - worked well for a while, but for modern sizes it is not possible to hold the table in memory
     34     - ![](9574c3243ae1aec42c16a87811967973.png)
     35 - I-nodes
     36     - just a FUCKTON of indirections
     37     - ![](989ec9c9f66e3d39587fe99eefeeb1f6.png)
     38 
     39 ## How to implement directories
     40 ![](d6e774bac420b1585709a558b8aba44f.png)
     41  ![](0d30522d012c79b891b3120ed9c2f8b3.png)
     42 
     43 FAT layout:
     44 
     45 - PBR stores "boot block"
     46 - reserved is later used for filesystem info
     47 - FAT #: preallocated file allocation table
     48 - preallocated root dir (FAT12/FAT16)
     49 - clusters are addressable blocks (FAT has chains indexed by starting cluster)
     50 - ![](555ca3a94b042070cc8360acf834fd98.png)
     51 
     52 UNIX dir entry:
     53 
     54 - dir entry stores only name and inode number
     55 - attributes are stored in inode
     56 - one inode per file, first inode is root
     57 - links:
     58     - hard link -- if 10 hard links to a file, then a single file with 10 dir entries pointing to that file (inode)
     59     - soft (symbolic) link -- if 10 soft links to a file, literally 10 files. can point to anything, but if file gets deleted, the link is dead.
     60 - where are the inode stored? it depends, as always.
     61 
     62  ![](1ce3484b2773ce6c1c6283327e880159.png)
     63 ![](0db1d8b55f787cdbab5a378ac5038ad0.png)
     64 ![](fc97a31fa9f8ded5eaa7caf1ad4720dc.png)
     65 
     66 how to manage disk space
     67 
     68 - linked list vs bitmap (linked list actually works really well here)
     69 
     70 ![](4ea0e1f1384708f15599dc2e8ac8c858.png)